#include <stdio.h>

long long fib_1(int x)
{
    if (x == 1) return 1;
    if (x == 2) return 2;
    if (x == 3) return 4;

    return fib_1(x-1) + fib_1(x-2) + fib_1(x-3);
}

long long fib_2(int x)
{
    int i;
    long long f1, f2, f3, tmp;

    if (x == 1) return 1;
    if (x == 2) return 2;
    if (x == 3) return 4;

    f1 = 4; f2 = 2; f3 = 1;
    for (i = 4; i < x; i ++)
    {
        tmp = f3;
        f3 = f2;
        f2 = f1;
        f1 = f2 + f3 + tmp;
    }

    return f1 + f2 + f3;
}

void mul(long long (*a)[3], long long (*b)[3])
{
    int i, j, k;
    long long t[3][3];

    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
        {
            t[i][j] = 0;
            for (k = 0; k < 3; k++)
                t[i][j] += a[i][k]*b[k][j];
        }

    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            a[i][j] = t[i][j];
}


long long fib_3(int x)
{
    int i, j;

    long long a[3][3] = {{1,1,0}, {1,0,1}, {1,0,0}};
    long long b[3][3] = {{1,0,0}, {0,1,0}, {0,0,1}};
    
    while (x)
    {
        if (x&1)
            mul(b, a);
        mul(a, a);
        x >>= 1;
    }

    return b[0][0];
}

int main(int argc, char const* argv[])
{
    printf("%lld\n", fib_1(34));
    printf("%lld\n", fib_2(1000));
    printf("%lld\n", fib_3(1000));
    
    return 0;
}
